package com.likeycy.my.list;

/**
 * @ClassName: MyLinkedList
 * @Description: TODO
 * @Author: sodagreen
 * @Date: 2021/3/3 19:25
 * @Version: 1.0
 */
public class MyLinkedList <E> extends AbstractList<E> implements List<E>{

    /** 头节点 */
    private Node<E> first;
    /** 尾节点 */
    private Node<E> last;

    /**
     * 存放数据且指向前后节点的实体
     *
     * @param <E>
     */
    private static class Node<E> {
        /** 存放的要添加的元素数据 */
        E element;
        /** 下一个节点 */
        Node<E> next;
        /** 上一个节点 */
        Node<E> prev;

        public Node(Node<E> prev, E element, Node<E> next) {
            this.prev = prev;
            this.element = element;
            this.next = next;
        }

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            if (prev != null) {
                sb.append(prev.element);
            } else {
                sb.append("null");
            }
            sb.append("_").append(element).append("_");
            if (next != null) {
                sb.append(next.element);
            } else {
                sb.append("null");
            }
            return sb.toString();
        }

        @Override
        protected void finalize() throws Throwable {
            System.out.println("LinkedList——Node<E>——finalize()，内存回收了");
        }
    }

    /**
     * 清空链表
     */
    @Override
    public void clear() {
        /*
        * 需要解决的问题：
        * 1、first和last变量未设置为null时，无法显式的释放内存空间，导致GC无法回收内存，占用内存
        */
        size = 0;
        first = null;
        last = null;
    }

    @Override
    public E get(int index) {
        /*
        * 需要解决的问题：
        * 1、只进行了初始化的空集合应该返回什么值？
        * 2、index索引不在集合的长度范围内该做什么？比如说负数或者超过集合长度。
        */
        return indexByCurrentNode(index).element;
    }

    @Override
    public E set(int index, E element) {
        // 先获取指定索引位置的Node节点
        Node<E> node = indexByCurrentNode(index);
        // 保存查找到的node里的element数据，然后再替换为新的数据
        E oldElementValue = node.element;
        node.element = element;
        return oldElementValue;
    }

    @Override
    public void add(int index, E element) {
        // index索引大于0或者超过size时抛出异常
        rangeCheckForAdd(index);
        /*
            添加会遇到的问题场景：
            1、集合内没有数据，size为0
                1.1 index为0时，新增节点插入后,此时first等于新增节点，last也等于新增节点
            2、集合内有数组，且size大于0
                2.1 index为0时，新增节点应该为新的first，新的first节点的perv应该为空，新的first的next应该为旧头节点，
                    且旧头节点的prev应该指向新的first。
                2.2 index不为0时，且index不等于size时。新增节点为新的中间节点。通过index获取指定index位置的指定节点，
                    指定Node节点为新增节点的next节点。新增节点的prev指向指定Node节点的上一个节点(prev)对象指向的下一个节点(next)。
                2.3 index不为0是，但index等于size。此时新增节点为新的last节点，新的last节点prev指向旧的尾节点，新的last节点的next
                    指向null。同时旧的last节点next指向新增的last节点
         */
        // 如果index==size,表示添加到链表的尾节点
        if (index == size) {
            // 此时last节点已经为旧的尾节点了，新增的节点将变成新的last节点
            Node<E> oldLast = last;
            // 新增节点并赋值给last遍历，让给新增的节点变成新last节点。同时新的last节点prev指向旧的last节点，且新的last节点prev指向null
            last = new Node<E>(oldLast, element, null);
            // 如果旧的last尾节点为空，那么表示当前链表内没有任何节点，即空集合。那么新增的节点即为last，也是first
            if (oldLast == null) {
                first = last;
            } else {
                // 如果就的last尾节点不为空，表示集合内存在元素，那么需要将为改变旧的last节点的next指向，让它指向新的last节点
                oldLast.next = last;
            }
        } else {
            // 先获取指定索引位置的Node节点。该节点会是准备新增节点的next节点
            Node<E> next = indexByCurrentNode(index);
            // 取出prev节点，该节点将会是新增节点的上一个节点
            Node<E> prev = next.prev;
            Node<E> newNode = new Node<E>(prev, element, next);
            // 新增节点完成后，旧节点的prev将指向新增节点
            next.prev = newNode;
            // 如果index为0，表示从头节点开始增加。那么此时新增的节点将会是新的first节点
            if (index == 0) {
                first = newNode;
            } else {
                // 如果index不为0，那就表示增加的是新增节点。那么我们需要拿出旧节点的prev节点，将prev节点的next指向新节点
                prev.next = newNode;
            }
        }
        size++;
    }

    @Override
    public E remove(int index) {
        /*
            删除会遇到的问题场景：
            1、集合为空，size==0
                1.1 index为0时，得到的first为null,调用first.element返回将会报空指针异常
            2、集合不为空, size > 1
                2.1 index==0时，要删除的则为first。那么first的next节点对象将会成为新的first节点，且
                    新的first节点的prev对象需要置为null
                2.3 index==size时，要删除的则为last，那么last的prev节点对象将会成为新的last节点。新的last节点
                    的next则需要置为null
            3、集合不为空，但size==1
                3.1 index正好等于0，删除的节点既是first也是last。删除后两个节点都需要置为null
         */
        Node<E> removeNode = indexByCurrentNode(index);
        Node<E> prev = removeNode.prev;
        Node<E> next = removeNode.next;
        // prev为空，表示要删除的节点一定是last节点，即index==0。
        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
        }

        // 如果next节点为空，那么表示要删除的节点一定是last节点，即index == size-1
        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
        }
        /*
            以上两个if有四种组合模式：
            1、true && true，即执行 first = next, last = prev。表示删除的链表节点既是头节点也是尾节点
            2、true && false，即执行的 first = next, next.prev = prev。表示删除的是链表的头节点
            3、false && true，即执行 prev.next = next, last = prev。表示删除的是链表的尾节点
            4、false && false，即执行的 prev.next = next, next.prev = prev。表示删除的是链表的中间节点
         */
        size--;
        return removeNode.element;
    }

    @Override
    public int indexOf(E element) {
        Node<E> node = first;
        if (element == null) {
            for (int i = 0; i < size; i++) {
                if (null == node.element) {
                    return i;
                }
                node = node.next;
            }
        } else {
            int i = 0;
            // 这里用两种循环方式遍历仅供参考
            while (null != node) {
                if (element.equals(node.element)) {
                    return i;
                }
                node = node.next;
                i++;
            }
        }
        return ELEMENT_NOT_FOUND;
    }

    /**
     * 根据指定的索引位置返回链表集合中当前位置上的Node节点对象
     *
     * @param index
     * @return
     */
    private Node<E> indexByCurrentNode(int index) {
        // 首先需要检查索引是否越界
        rangeCheck(index);
        /*
          遍历查找集合中指定index索引位置的需要解决的问题：
          1、index索引值为0
          2、index索引值接近头节点范围
          3、index索引值接近尾节点范围
          解决方式：
          index为0时，直接返回first节点。
          先用size长度除以2，得到index索引值范围是靠近头节点还是尾节点，然后选择从头节点开始遍历或
          从尾节点开始遍历。
         */
        Node<E> node = first;
        int capacityIfFlag = size >> 1;
        if (index < capacityIfFlag) {
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
        } else {
            node = last;
            for (int i = size-1; i > index; i--) {
                node = node.prev;
            }
        }
        return node;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("size=").append(size);
        sb.append(", ").append(this.getClass().getSimpleName()).append(", [");
        Node<E> node = first;
        for (int i = 0; i < size; i++) {
            if (i != 0) {
                sb.append(", ");
            }
            sb.append(node);
            node = node.next;
        }
        sb.append(']');
        return sb.toString();
    }

}
